package problems.contest;

/**
 * <p>https://leetcode.cn/contest/weekly-contest-313</p>
 *
 * @author habitplus
 * @since 9:53, 2022/10/2
 */
public class WCT313 {
    // 第一题: 6192. 公因子的数目
    public int commonFactors(int a, int b) {
        int min = Math.min(a, b);
        int ret = 1;
        for (int i = 2; i <= min; ++i) {
            if (a % i == 0 && b % i == 0) ++ret;
        }

        return ret;
    }


    // 第二题: 6193. 沙漏的最大总和
    public int maxSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int sum;
        int ret = 0;
        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                sum = 0;
                sum += grid[i][j] + grid[i][j + 1] + grid[i][j + 2];
                sum += grid[i + 1][j + 1];
                sum += grid[i + 2][j] + grid[i + 2][j + 1] + grid[i + 2][j + 2];
                ret = Math.max(ret, sum);
            }
        }

        return ret;
    }


    // 第三题: 6194. 最小 XOR
    // 贪心
    public int minimizeXor(int num1, int num2) {
        int n2 = Integer.bitCount(num2);


        char[] chs = Integer.toBinaryString(num1).toCharArray();

        int k = 0;
        // 先取最高位
        for (; k < chs.length && n2 > 0; ++k) {
            if (chs[k] == '1') {
                --n2;
            }
        }

        if (n2 <= 0) {
            // 低位置零
            while (k < chs.length) chs[k++] = '0';
            return Integer.parseInt(String.valueOf(chs), 2);
        }

        // 还有多余的 1，先从低位或 ‘0’ 位置开始填 1
        for (int i = chs.length - 1; i >= 0 && n2 > 0; --i) {
            if (chs[i] == '0') {
                chs[i] = '1';
                --n2;
            }
        }

        StringBuilder sb = new StringBuilder();
        while (n2-- > 0) sb.append('1');
        sb.append(String.valueOf(chs));

        return Integer.parseInt(sb.toString(), 2);
    }

    public static void main(String[] args) {
//        System.out.println(Integer.bitCount(5));
//        System.out.println(Integer.bitCount(-1));
//        System.out.println((1 ^ 0));

        System.out.println(new WCT313().minimizeXor(3,5));
        System.out.println(new WCT313().minimizeXor(1,12));
    }


}
